package Sort;

import java.text.SimpleDateFormat;
import java.util.Date;
/*
插入排序
 */
public class InsertSelect {

  public static void main(String[] args) {
//    int num[] = new int[]{101,34,119,1};
//    insertSelect(num);


    int num[] = new int[80000];
    for (int i = 0; i < 80000; i++) {
      num[i] = (int)(Math.random()*80000);//生成一个0到80000的数
    }
//    测试插入排序的效率
    Date date = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy--MM-dd HH:mm:ss");
    String dateStr1 = simpleDateFormat.format(date);
    System.out.println("排序前的时间：" + dateStr1);

//    排序后
    insertSelect(num);

    Date date2 = new Date();
    String dateStr2 = simpleDateFormat.format(date2);
    System.out.println("排序后的时间：" + dateStr2);
  }

  public static void insertSelect(int[] num){
    for (int i = 1; i < num.length; i++) {//从第二位开始排序，第一位不管是从小还是从大排序，都是有序的
      int temp = num[i];//假定最小的是当前的数
      int minIndex = i;//最小的数的下标，方便后边交换数字
      while (minIndex > 0 && temp < num[minIndex - 1]){
        num[minIndex] = num[minIndex - 1];
        minIndex--;
      }
      if (minIndex != i){
        num[minIndex] = temp;
      }
//      System.out.println("第"+ i + "次排序后的结果：" + Arrays.toString(num));
    }
  }
}
